#!/usr/bin/env python3

"""
Given a collection of intervals, merge all overlapping intervals

Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
"""

class Solution:
    def merge(self, intervals):
        self.quick_sort(intervals, 0, len(intervals))
        result = []
        scope_start = None
        scope_end = None
        for val in intervals:
            if scope_start is not None:
                if scope_end < val[0]:
                    result.append([scope_start, scope_end])
                    scope_start = None
                    scope_end = None
                else:
                    scope_end = max(val[1], scope_end)
            if scope_start is None:
                scope_start = val[0]
                scope_end = val[1]
        else:
            if scope_start is not None:
                result.append([scope_start, scope_end])
        return result
            
                

    def quick_sort(self, intervals, start_index, end_index):
        if end_index - start_index <= 1:
            return
        start = start_index
        end = end_index - 1
        last = intervals[end]
        from_end = True
        while start != end:
            if from_end:
                start_val = intervals[start]
                if start_val[0] > last[0]:
                    intervals[start], intervals[end] = intervals[end], intervals[start]
                    from_end = False
                    end -= 1
                else:
                    start += 1
            else:
                end_val = intervals[end]
                if end_val[0] < last[0]:
                    intervals[start], intervals[end] = intervals[end], intervals[start]
                    from_end = True
                    start += 1
                else:
                    end -= 1
        self.quick_sort(intervals, start_index, end)
        self.quick_sort(intervals, end + 1, end_index)

if __name__ == '__main__':
    s = Solution()
    a = [[4,5],[2,4],[4,6],[3,4],[0,0],[1,1],[3,5],[2,2]]
    print(str(s.merge(a)))
    raise Exception()
    print(str(s.merge([[1, 4], [2, 3]])))
    input = [[1, 3], [2, 6], [8, 10], [15, 18]]
    print(str(s.merge(input)))
    print(str(s.merge([[3, 1], [2, 6], [9, 10], [1, 2]])))
